package com.cat.dataStructure03;

/**
*   @description https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
*   @author 曲大人的喵
*   @create 2025/11/11 17:54
*   @since JDK17
*/

public class Solution45 {
    public int strStr(String haystack, String needle) {
        return kmp(haystack.toCharArray(), needle.toCharArray());
    }
    int[] nextArray(char[]s, int m) {
        if (m == 1) {
            return new int[] {-1};
        }
        int[] next = new int[m];
        next[0] = -1;
        next[1] = 0;
        int i = 2, cn = 0;
        while (i < m) {
            if (s[i - 1] == s[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {    // 往前面跳
                cn = next[cn];
            } else {    // 跳到0还没匹配上意味着匹配不了了
                next[i++] = 0;
            }
        }

        return next;
    }
    int kmp(char[] s1, char[] s2) {
        int n = s1.length, m = s2.length, x = 0, y = 0;
        int[] next = nextArray(s2, m);
        while (x < n && y < m) {
            if (s1[x] == s2[y]) {
                x++;
                y++;
            } else if (y == 0) {
                x++;
            } else {
                y = next[y];
            }
        }
        return y == m ? x - y : -1;
    }

}
